Trong
lý thuyết độ phức tạp tính toán, lớp
NC (viết tắt cho "Nick's Class") là tập hợp các
bài toán quyết định giải được trong thời gian đa thức của lôgarit trên
máy tính song song với số bộ xử lý là đa thức. Nói cách khác, một bài toán nằm trong
NC khi và chỉ khi tồn tại hằng số c và k sao cho nó có thể giải trong thời gian O ( log c n ) {\displaystyle O(\log ^{c}n)} bằng O ( n k ) {\displaystyle O(n^{k})} bộ xử lý.
Stephen Cook đưa ra tên gọi "Nick's Class" theo tên của
Nick Pippenger, người đã có nhiều nghiên cứu về mạch logic với chiều sâu đa thức của lôgarit và kích thước đa thức.
[1]Cũng như
P được xem là lớp các bài toán có thể giải hiệu quả trên máy thông thường,
NC được xem là lớp các bài toán giải được hiệu quả trên máy song song.
NC là tập hợp con của
P do tính toán song song trong thời gian đa thức của lôgarit có thể được giả lập trên máy thông thường trong thời gian đa thức. Vẫn chưa biết liệu
NC và
P có bằng nhau hay không.Máy tính song song thường được định nghĩa là một máy song song, truy cập ngẫu nhiên (mô hình
PRAM, viết tắt tên tiếng Anh parallel random-access machine). Trong mô hình này, máy có bộ nhớ sử dụng chung cho các bộ xử lý, và mỗi bộ xử lý có thể truy cập bất kì địa chỉ bộ nhớ nào trong thời gian hằng số. Định nghĩa của
NC không phụ thuộc vào lựa chọn cách PRAM xử lý việc nhiều bộ xử lý truy cập cùng một lúc một địa chỉ bộ nhớ (có thể là CRCW, CREW, hay EREW).Một cách tương đương,
NC là tập hợp những bài toán quyết định được bởi các mạch logic đồng dạng với chiều sâu đa thức của lôgarit và số cổng là đa thức.